package com.meterhuang;

import lombok.extern.slf4j.Slf4j;

import java.util.HashMap;
import java.util.Map;

/**
 * 旋转数组[middle]
 * 假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
 * 说明：这个数组已被旋转过很多次了，次数不详
 *
 * 旋转数组的解释：
 * 给定一个有序数组，将数组中的元素向右移动k位，k为非负数
 * 如：[1,2,3,4,5,6,7],k=3
 *  [5,6,7,1,2,3,4]
 *
 * 示例1:
 * 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 * 输出: 8（元素5在该数组中的索引）
 * 如果没有找到返回-1
 *
 * 来源：https://leetcode-cn.com/problems/search-rotate-array-lcci
 *
 *
 * @author meterhuang
 * @date 2021/04/08 15:56
 */
@Slf4j
public class RotateArray {

	public static void main(String[] args) {
		int search = search(new int[]{6,14,15, 16, 19, 20, 25, 1, 3, 5, 5, 6}, 5);
		log.info("result: {}", search);
		// 二分查找总体上效率更高
		search = binarySearch(new int[]{6,14,15, 16, 19, 20, 25, 1, 3, 5, 5, 6}, 5);
		log.info("result: {}", search);
	}

	/**
	 * 简单解法：map
	 * @param arr
	 * @param target
	 * @return
	 */
	public static int search(int[] arr, int target) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int index = 0; index < arr.length; ++index) {
			Integer current = map.get(arr[index]);
			if (current == null || current > index) {
				map.put(arr[index], index);
			}
		}

		Integer result = map.get(target);
		return result == null ? -1 : result;
	}

	/**
	 * 二分查找: 旋转数组不一定是有序的，对于二分需要做特殊处理，否则可能找不到元素
	 * [二分查找的使用对象是有序序列]
	 * @param arr
	 * @param target
	 * @return
	 */
	public static int binarySearch(int[] arr, int target) {
		int start = 0;
		int end = arr.length - 1;
		//确保不会出现重复查找，越界
		while (start <= end) {
			int middle = (start + end) / 2;
			if (arr[start] == target) {
				return start;
			} else if (arr[middle] == target) {
				end = middle;
			} else if (arr[end] == target) {
				start = middle + 1;
			} else if (arr[middle] > arr[end]) {
				// 说明左边有序，左半边单调
				// target在左边范围
				if (target > arr[start] && target < arr[middle]) {
					end = middle - 1;
				} else {
					start = middle + 1;
				}
			} else if (arr[middle] < arr[end]) {
				// 说明右边有序，右半边单调
				// target刚好在右边范围
				if (target > arr[middle] && target < arr[end]) {
					start = middle + 1;
				} else {
					end = middle - 1;
				}
			} else {
				// 特殊情况，左边跟右边相等，暴力搜索，将右边界缩短一个位置
				end = end - 1;
			}
		}
		return -1;
	}

	/**
	 * 直接遍历，因为是寻找最小索引，匹配到直接返回
	 * @param arr
	 * @param target
	 * @return
	 */
	public static int searchV2(int[] arr, int target) {
		for (int index = 0; index < arr.length; ++index) {
			if (arr[index] == target) {
				return index;
			}
		}
		return -1;
	}

	/**
	 * 二分法查找经典实现
	 * @param srcArray
	 * @param des
	 * @return
	 */
	public static int classicBinarySearch(Integer[] srcArray, int des) {
		//定义初始最小、最大索引
		int start = 0;
		int end = srcArray.length - 1;
		//确保不会出现重复查找，越界
		while (start <= end) {
			//计算出中间索引值
			int middle = (end + start) / 2 ;
			if (des == srcArray[middle]) {
				return middle;
				//判断下限
			} else if (des < srcArray[middle]) {
				end = middle - 1;
				//判断上限
			} else {
				start = middle + 1;
			}
		}
		//若没有，则返回-1
		return -1;
	}

}
